/* ************************************************************************
> File Name:     bst.c
> Author:        zhfu
> mail:          3346897597@qq.com
> Created Time:  2022年05月04日 星期三 17时13分31秒
> Description:   
 ************************************************************************/
#include<stdlib.h>
#include<stdio.h>
#include"bst.h"

static link make_node(unsigned char item)
{
    link p = malloc(sizeof *p);
    p->item = item;
    p->l = NULL;
    p->r = NULL;

    return p;
}

static void free_node(link p)
{
    free(p);
}

link search(link t, unsigned char key)
{
    if (!t){
        return NULL;
    }

    if (t->item == key){
        return t;
    }

    link p1, p2;
    if (t->item < key){
        p1 = search(t->r, key);
        return p1;
    }
    else{
        p2 = search(t->l, key);
        return p2;
    }
}

link insert(link t, unsigned char key)
{
    if (!t){
        t = make_node(key);
        return t;
    }

    if (t->item <= key){
        t->r = insert(t->r, key);
    }
    else{
        t->l = insert(t->l, key);
    }

    return t;
}

link delete(link t, unsigned char key)
{
    link p;
    if (!t){
        return NULL;
    }

    if (t->item < key){
        t->r = delete(t->r, key);
    }
    else if (t->item > key){
        t->l = delete(t->l, key);
    }
    else{
        if (t->l == NULL && t->r == NULL){
            free_node(t);
            t = NULL;
        }
        else if (t->l){
           for (p = t->l; p->r; p = p->r);
           t->item = p->item;
           t->l = delete(t->l, p->item);
        }
        else{
            for (p = t->r; p->l; p = p->l);
            t->item = p->item;
            t->r = delete(t->r, p->item);
        }
    }

    return t;
}

void print_tree(link t)
{
	if (t) {
		printf("(");
		printf("%d", t->item);
		print_tree(t->l);
		print_tree(t->r);
		printf(")");
	} else
		printf("()");
}
